package com.spring.share.algorithm;

public class LongestCommonSubsequence {

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence("abcde", "ace"));
    }

    public static int longestCommonSubsequence(String text1, String text2) {

        int[][] table = new int[text1.length() + 1][text2.length() + 1];

        // 初始化第一行全部为0
        for (int col = 0; col < table[0].length; col++) {
            table[0][col] = 0;
        }

        // 初始化第一列全部为0
        for (int row = 0; row < table.length; row++) {
            table[row][0] = 0;
        }
        for (int i = 1; i <= text1.length(); i++) {
            char rowChar = text1.charAt(i-1);
            for (int j = 1; j <= text2.length(); j++) {
                char colChar = text2.charAt(j-1);
                if (rowChar == colChar) {
                    // 相等则等于 斜上角的数据 + 1
                    table[i][j] = table[i-1][j-1] + 1;
                } else {
                    table[i][j] = Math.max(table[i][j-1], table[i-1][j]);
                }
            }
        }
        // 返回最后一个单元格的数据
        return table[text1.length()][text2.length()];
    }
}
